package code.D1221;

import java.util.ArrayList;
import java.util.List;

/**
 * author： yeswater
 * create： 2023/12/22
 * <p>
 * 找到字符串中所有字母异位词
 */
public class T438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length(), m = p.length();
        // c1 统计p的磁盘词频 c2 统计 s 的词频
        int[] c1 = new int[26], c2 = new int[26];
        for (int i = 0; i < m; i++) {
            c2[p.charAt(i) - 'a']++;
        }
        for (int l = 0, r = 0; r < n; r++) {
            c1[s.charAt(r) - 'a']++;
            if (r - l + 1 > m) c1[s.charAt(l++) - 'a']--;
            if (check(c1, c2)) {
                ans.add(l);
            }
        }
        return ans;
    }
    
    private boolean check(int[] c1, int[] c2) {
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) {
                return false;
            }
        }
        return true;
    }
}
